package arrayList;

import java.util.Arrays;

public class MyArrayList<E> {

    private Object[] elementData;// 数组
    private int usedSize;// 代表有效的数据个数
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    public MyArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    public MyArrayList(int capacity) {
        // 判断参数的合法性
        if (capacity >= 0) {
            this.elementData = new Object[capacity];
        }else {
            throw new RuntimeException("初始化的容量不能为负数！");
        }
    }

    /**
     * 添加元素
     * @param e 要添加的元素
     */
    public boolean add(E e) {
        // 确定一个真正的容量,预测 -> 如需扩容则扩容
        ensureCapacityInternal(usedSize + 1);
        // 扩容完毕，放数据
        elementData[usedSize++] = e;
        return true;
    }

    /**
     * 给 index位置添加元素
     * @param index
     * @param e
     */
    public boolean add(int index, E e) {
        // 检查 index 是否合法
        rangeCheckForAdd(index);
        // 确定一个真正的容量 -> 如需扩容则扩容
        ensureExplicitCapacity(usedSize + 1);
        // 移动 index后面的元素,并在 index位置插入元素
        copy(index,e);
        usedSize++;
        return true;
    }
    private void copy(int index, E e){
        for (int i = usedSize; i > index; i--) {
            elementData[i] = elementData[i - 1];
        }
        elementData[index] = e;
    }
    private void rangeCheckForAdd(int index) {
        if (index > usedSize || index < 0)
            throw new IndexOutOfBoundsException("index位置不合法！");
    }



    public void ensureCapacityInternal(int minCapacity) {
        // 计算出需要的容量
        int capacity = calculateCapacity(elementData, minCapacity);
        // 根据计算出的容量，看是否需要扩容或者分配内存
        ensureExplicitCapacity(capacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        // 如果需要的容量大于数组容量，就扩容
        if (minCapacity - elementData.length > 0)
            // 扩容
            grow(minCapacity);
    }

    private static final int MAX_ARRAY_SIZE  = Integer.MAX_VALUE - 8;
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            // 说明你要的容量非常大，就分配更大的内存
            newCapacity = hugeCapacity(minCapacity);;
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 确定之前数组是否分配过内存，没有的话返回一个初始化的容量 10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(10, minCapacity);
        }
        // 分配后，返回 +1 后的值，即实际所需要的容量
        return minCapacity;
    }
}
